The present invention relates to a pattern matching system available for various systems such as speech recognition system.
There have been proposed various technologies of the pattern matching in speech recognition; the DP (dynamic programming) matching method disclosed in U.S. Pat. No. 3,816,722 is one of the most popularly used methods. The clockwise DP method disclosed in U.S. Pat. No. 4,592,086 is a continuous speech recognition method with syntax control or an isolated speech recognition method. For simplicity's sake, description will be given herein only to the clockwise DP method of the type for isolated speech recognition.
A set of words is assumed to be an object of recognition wherein the name of a word is designated by a numerical number n. EQU {n.vertline.n=1, 2, . . . N}
A reference pattern is prepared for each word as below: EQU B.sup.n =b.sub.1.sup.n, b.sub.2.sup.n . . . b.sub.j.sup.n. . . b.sub.j.sup.n n
wherein j denotes a time point, and b.sub.j.sup.n a feature of the reference pattern B.sup.n at the time point j.
An input speech pattern is expressed similarly as below: EQU A=a.sub.1, a.sub.2 . . . a.sub.i . . . a.sub.I
Speech recognition is performed by calculating the distance between the input pattern A and the reference pattern B.sup.n, and determining the word n giving the minimum cumulative distance as the recognition result.
In the DP matching method, the above cumulative distance is calculated by the dynamic programming (DP) as follows:
.smallcircle. initial conditions EQU g.sup.n (1, 1)=d.sup.n (1, 1) (1)
.smallcircle. recurrence formula ##EQU1##
.smallcircle. distance D(A, B.sup.n) between patterns is determined in accordance with the formula (3). EQU D(A, B.sup.n)=g.sup.n (I, J.sup.n) (3)
wherein d.sup.n (i, j) denotes the distance between features a.sub.i and b.sub.j.sup.n i.e., .parallel.a.sub.i -b.sub.n.sup.n .parallel.. A cumulative distance is expressed by g.sup.n (i, j) and is called an optimal cumulative distance.
The DP matching process was initially executed for each word, but is improved later in the clockwise DP method so as to be executed in parallel for plural words respectively. More particularly, in the clockwise DP method the optimal cumulative value g.sup.n (i, j) is calculated for n and j specified by all the combinations of n and j for each time i of the input pattern in a space defined by i, j and n as shown in FIG. 1 with increasing the time i to complete the process.
In practice, however, it is not necessary to prepare work areas for all the spaces. The calculation of the formula (2) can be proceeded with the work areas for two time points, i.e., i and (i-1). This clockwise DP method is excellent in real-time processing with shorter response time since the process can be executed in synchronization with the input of feature a.sub.i of the input pattern.
However, in the DP matching method, the amount of the distance calculation still causes problem: the features a.sub.i and b.sub.j.sup.n are generally vectors of ten or higher dimension order, and it is an extremely heavy load for an ordinary hardware to conduct the distance calculations of ##EQU2## times within one clock (usually about 10 ms).
In order to solve the problem, L. R. Rabiner et al have proposed a method using vector quantization in a paper entitled "On the Performance of Isolated Word Speech Recognizers Using Vector Quantization and Temporal Energy Contours", AT&T Bell Laboratories Technical Journal, Vol. 63, No. 7, September issue, 1984. pp. 1,245-1,260. In the method, a set {C.sub.k } of code vectors is prepared. The features {b.sub.j.sup.n } of the reference pattern is approximated by the code vectors. Namely, each reference pattern B.sup.n is expressed as a time series of the number k=k(n, j) specifying the code vector C.sub.k is the most similar to each b.sub.j.sup.n. Then, the distance D(k) between the feature a.sub.i of the input pattern and each code vector is calculated and stored in a table during the time of DP matching processing. At the time of recurrence formula calculation, the formula (2) is calculated with reference to the equation (4). EQU d.sup.n (i, j)=D(k(n, j)) (4)
The distance calculation amount can be reduced by employing the vector quantization method, but not to a satisfactory extent.
In general, the required number of code vectors is more than 256 for maintaining the good recognition rate. If it is assumed that one calculation of D(i, k) requires 40 .mu.s, the calculation for 256 vectors would take 10 ms. In other words, one clock for i (10 ms) is almost completely consumed by the calculation of vector distance to leave no time for recurrence formula calculation. For this reason, a high speed hardware specially designed for the purpose has heretofore been used for executing DP matching.
Moreover, when the above-mentioned clockwise DP method is used for recognition of large vocabularly speech, the work area inevitably becomes large in order to retain g.sup.n (i, j) and the calculation amount is enormous. More specifically, the recurrence formula (2) should be executed and stored for all the combinations of n and j within one cycle of i. Where the reference pattern length is J.sup.n =30, and N=1000 words are to be recognized, the formula (2) should be calculated at the points in the number of as many as 3.times.10.sup.4 and the result should be retained.